// 题目描述：
// 给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。

// 每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:

// 0 <= j <= nums[i] 
// i + j < n
// 返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。



// 示例 1:

// 输入: nums = [2,3,1,1,4]
// 输出: 2
// 解释: 跳到最后一个位置的最小跳跃数是 2。
//      从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
// 示例 2:

// 输入: nums = [2,3,0,1,4]
// 输出: 2

// 自己的答案(答案错误，没解出来)：
/**
 * @param {number[]} nums
 * @return {number}
 */
var jump = function (nums) {
    // let count = 0
    // const calculateNums = (i) => {
    //     if(i === nums.length - 1) {
    //         return 0
    //     }
    //     for (let j = i; j < i + nums[i]; j++) {
    //         if (nums[j] + j === nums.length - 1) {
    //             count++
    //             return count
    //         }
    //     }
    // }
    // for (let i = 0; i < nums.length; i++) {
    //     if (nums[i] + i === nums.length - 1) {
    //         count++
    //         return count
    //     } else {
    //         calculateNums(i)
    //     }

    // }
    // return count

    // let i = nums.length
    // let count = 0
    // let wholeI = nums.length - 1
    // while(i--) {
    //     if(nums[i] + i === wholeI) {
    //         wholeI = i
    //         count++
    //     }
    // }
    // return wholeI === 0 ? count : 0
};


// Gpt答案：
// 代码解释：
// 变量初始化：
// n：数组的长度。
// jumps：记录跳跃次数，初始化为0。
// currentEnd：当前跳跃能够到达的最远位置，初始化为0。
// farthest：在当前跳跃范围内能够到达的最远位置，初始化为0。
// 遍历数组：
// 从数组的第一个元素开始遍历，直到倒数第二个元素（因为我们要到达的是nums[n - 1]）。
// 在每次遍历中，更新farthest为当前位置i加上nums[i]所能到达的最远位置。
// 检查是否需要跳跃：
// 当遍历到currentEnd时，表示需要进行一次跳跃。
// 增加跳跃次数jumps。
// 更新currentEnd为farthest，即当前跳跃能够到达的最远位置。
// 如果currentEnd已经到达或超过数组的最后一个位置，则提前结束循环。
// 返回结果：
// 返回跳跃次数jumps。
function jump(nums) {
    const n = nums.length;
    if (n <= 1) return 0;

    let jumps = 0;
    let currentEnd = 0;
    let farthest = 0;

    for (let i = 0; i < n - 1; i++) {
        farthest = Math.max(farthest, i + nums[i]);

        if (i === currentEnd) {
            jumps++;
            currentEnd = farthest;

            if (currentEnd >= n - 1) {
                break;
            }
        }
    }

    return jumps;
}

// 示例测试用例
console.log(jump([2, 3, 1, 1, 4])); // 输出: 2
console.log(jump([2, 3, 0, 1, 4])); // 输出: 2

// 官方题解：
/**
 * @param {number[]} nums
 * @return {number}
 */
var jump = function (nums) { // 动态规划，不懂
    if (nums.length < 3) {
        return nums.length - 1;
    }
    const dp = new Array(nums.length).fill(Infinity);
    dp[0] = 0;
    dp[1] = 1;
    for (let i = 2; i < nums.length; i++) {
        for (let j = i - 1; j >= 0; j--) {
            // 往前找，找到能走到当前位置的， + 1代表走一步到当前位置
            // 找最小值
            if (j + nums[j] >= i) {
                dp[i] = Math.min(dp[i], dp[j] + 1);
            }
        }

    }
    return dp[dp.length - 1];
};

var jump = function (nums) { // 类似 Gpt
    let curIndex = 0
    let nextIndex = 0
    let steps = 0
    for (let i = 0; i < nums.length - 1; i++) {
        nextIndex = Math.max(nums[i] + i, nextIndex)
        if (i === curIndex) {
            curIndex = nextIndex
            steps++
        }
    }

    return steps
};